package com.pan.alg.leecode;

/**
 * @author by panstark
 * @description
 * @notice
 * @date 2022/1/18
 */
public class BiggestCommonNum {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int
     * @param b int
     * @return int
     */
    public static  int gcd (int a, int b) {
        if(a==1||b==1){
            return 1;
        }
        int numbig = 0;
        // write code here
        for(int i=1;i<=a;i++){
            if(a%i==0&&b%i==0){
                numbig=i;
            }
        }
        return numbig;
    }

    public static  int gcd2 (int a, int b) {
        if(a==1||b==1){
            return 1;
        }
        int numbig = 1;
        int max = a>b?a:b;
        int min = a>b?b:a;
        int i=2;
        while(i<=min){
            if(max%i==0&&min%i==0){
                max/=i;
                min/=i;
                numbig*=i;
                i=2;
            }else{
                i++;
            }
        }

        return numbig;
    }

    public static void main(String[] args) {
        //long start = System.currentTimeMillis();
        //int gcd = gcd(1000000000, 1000000000);

        //System.out.println("gcb:"+gcd+"耗时："+(System.currentTimeMillis()-start));

        long start2 = System.currentTimeMillis();
        int gcd2 = gcd2(1000000000, 1000000000);
        System.out.println("gcb2:"+gcd2+"耗时2："+(System.currentTimeMillis()-start2));
    }
}
